from typing import *


def z(s: str):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        z[i] = 0 if i > r else min(z[i - l], r - i + 1)
        while (j := i + z[i]) < n and s[z[i]] == s[j]:
            l, r = i, j
            z[i] += 1
    return z


s = "aaaaaa"
print(z(s))


def kmp_next(s):
    n = len(s)
    next = [0] * n
    l = 0  # l 是i-1位置后缀和前缀相同的长度，也是当前i比较的位置
    for i in range(1, n):
        while l > 0 and s[l] != s[i]:
            l = next[l - 1]
        if s[i] == s[l]:
            l += 1
        next[i] = l
    return next


print(kmp_next("abcde"))
